Ch.11 Change of Basis

Find the change of basis matrix for the following bases $B,D\in\mathcal{P}_2$
$B=\langle1,1+x,1+x+x^2\rangle\space D=\langle x^2-1,x,x^2+1\rangle$

Call the matrix $M$. Since this is an identity map,
$M(1)=\text{Rep}_D(1)=\begin{pmatrix}-1/2\\0\\1/2\end{pmatrix}$
$M(1+x)=\text{Rep}_D(1+x)=\begin{pmatrix}-1/2\\1\\1/2\end{pmatrix}$
$M(1+x+x^2)=\text{Rep}_D(1+x+x^2)=\begin{pmatrix}0\\1\\1\end{pmatrix}$
So,
$\text{Rep}_{B,D}(\text{id})=\begin{pmatrix}-1/2&-1/2&0\\0&1&1\\1/2&1/2&1\end{pmatrix}$

Now, suppose we want to take $\vec{v}=3+2x+4x^2$
$\text{Rep}_B(\vec{v})=\begin{pmatrix}1\\-2\\4\end{pmatrix}$
Then we can change basis to $D$ by multiplying
$\text{Rep}_D(\vec{v})=\begin{pmatrix}-1/2&-1/2&0\\0&1&1\\1/2&1/2&1\end{pmatrix}\begin{pmatrix}1\\-2\\4\end{pmatrix}=\begin{pmatrix}1/2\\2\\7/2\end{pmatrix}$
And indeed,
$1/2(x^2-1)+2(x)+7/2(x^2+1)=3+2x+4x^2=\vec{v}$

For the forward direction, we must prove $M$ chnages basis $\implies$$M$ is nonsingular.
Since changing from basis $B$ to $D$ is invertible (changing from basis $D$ to $B$), the $M$ must also be invertible, therefore it is nonsingular.
For the reverse direction, we must prove $M$ is nonsingular $\implies$ M is a change of basis matrix.
For this, since $M$ is nonsingular,it is a product of elementary reduction matrices (see Ch.10 for proof), so we only need to show that each elementary reduction matrix changes basis.
First, the matrix which multiplies row $i$ by a constant $k$ changes basis from $\langle\vec{\beta}_1,...,\vec{\beta}_i,...,\vec{\beta}_n\rangle$ to $\langle\vec{\beta}_1,...,\frac{1}{k}\vec{\beta}_i,...,\vec{\beta}_n\rangle$
$\begin{array}{rcccl}\vec{v}&=&c_1\vec{\beta}_1+\cdots+c_i\vec{\beta}_i+\cdots+c_n\vec{\beta}_n&&\\&=&c_1\vec{\beta}_1+\cdots+kc_i(\frac{1}{k}\vec{\beta}_i)+\cdots+c_n\vec{\beta}_n&=&\vec{v}\end{array}$

For the matrix that swaps two rows, the corresponding basis vectors also simply swap.

For the matrix that adds a multiple of one row to another (i.e. $kc_i+c_j$), the basis changes from $\langle\vec{\beta}_1,...,\vec{\beta}_i,...,\vec{\beta}_j,...,\vec{\beta}_n\rangle$ to $\langle\vec{\beta}_1,...,\vec{\beta}_i-k\vec{\beta}_j,...,\vec{\beta}_j,...,\vec{\beta}_n\rangle$
$\begin{array}{rcccl}\vec{v}&=&c_1\vec{\beta}_1+\cdots+c_i\vec{\beta}_i+\cdots+c_j\vec{\beta}_j+\cdots+c_n\vec{\beta}_n&&\\&=&c_1\vec{\beta}_1+\cdots+c_i(\vec{\beta}_i-k\vec{\beta}_j)+\cdots+(kc_i+c_j)\vec{\beta}_j+\cdots+c_n\vec{\beta}_n&=&\vec{v}\end{array}$
(notice that $kc_i\vec{\beta}_j$ cancels out)
So, applying an elementary reduction matrix changes basis, so any invertible matrix must be a change of basis matrix.

Consider the transformation map $h:\mathbb{R}^3\to\mathbb{R}^3$ represented by $\text{Rep}_{\mathcal{E}_3,\mathcal{E}_3}(h)=H=\begin{pmatrix}1&0&2\\0&1&1\\1&2&3\end{pmatrix}$
This represents a transformation that takes a vector $\begin{pmatrix}1\\1\\1\end{pmatrix}$ to a different vector like $\begin{pmatrix}3\\2\\6\end{pmatrix}$
(note: both are with respect to the standard basis)
$\begin{pmatrix}1\\1\\1\end{pmatrix}\xmapsto{h}\begin{pmatrix}3\\2\\6\end{pmatrix}$

Suppose we want to convert to the basis
$\hat{B}=\hat{D}=\langle\begin{pmatrix}1\\0\\0\end{pmatrix},\begin{pmatrix}1\\1\\0\end{pmatrix},\begin{pmatrix}1\\1\\1\end{pmatrix}\rangle$
Under this basis, $\begin{pmatrix}1\\1\\1\end{pmatrix}_{\mathcal{E}_3}=\begin{pmatrix}0\\0\\1\end{pmatrix}_{\hat{B}}$ and $\begin{pmatrix}3\\2\\6\end{pmatrix}_{\mathcal{E}_3}=\begin{pmatrix}1\\-4\\6\end{pmatrix}_{\hat{B}}$ so
$\begin{pmatrix}0\\0\\1\end{pmatrix}_{\hat{B}}\xmapsto{h}\begin{pmatrix}1\\-4\\6\end{pmatrix}_{\hat{B}}$
This is the same map, but under a different representation. We want to find the matrix representation of this map, $\hat{H}$

First find $\text{Rep}_{\hat{B},\mathcal{E}_3}(\text{id})$
$\begin{pmatrix}1\\0\\0\end{pmatrix}_{\hat{B}}=\begin{pmatrix}1\\0\\0\end{pmatrix}_{\mathcal{E}_3},\space\begin{pmatrix}0\\1\\0\end{pmatrix}_{\hat{B}}=\begin{pmatrix}1\\1\\0\end{pmatrix}_{\mathcal{E}_3},\space\begin{pmatrix}0\\0\\1\end{pmatrix}_{\hat{B}}=\begin{pmatrix}1\\1\\1\end{pmatrix}_{\mathcal{E}_3}$
$\implies\text{Rep}_{\hat{B},\mathcal{E}_3}(\text{id})=\begin{pmatrix}1&1&1\\0&1&1\\0&0&1\end{pmatrix}$

Next we find $\text{Rep}_{\mathcal{E}_3,\hat{B}}(\text{id})$
$\begin{pmatrix}1\\0\\0\end{pmatrix}_{\mathcal{E}_3}=\begin{pmatrix}1\\0\\0\end{pmatrix}_{\hat{B}},\space\begin{pmatrix}0\\1\\0\end{pmatrix}_{\mathcal{E}_3}=\begin{pmatrix}-1\\1\\0\end{pmatrix}_{\hat{B}},\space\begin{pmatrix}0\\0\\1\end{pmatrix}_{\mathcal{E}_3}=\begin{pmatrix}0\\-1\\1\end{pmatrix}_{\hat{B}}$
$\implies\text{Rep}_{\mathcal{E}_3,\hat{B}}(\text{id})=\begin{pmatrix}1&-1&0\\0&1&-1\\0&0&1\end{pmatrix}$
You can also use the fact that
$\text{Rep}_{\mathcal{E}_3,\hat{B}}(\text{id})=(\text{Rep}_{\hat{B},\mathcal{E}_3}({\text{id}}))^{-1}$
since the inverse of $\text{id}$ is $\text{id}$

Finally, we have
$\hat{H}=\begin{pmatrix}1&-1&0\\0&1&-1\\0&0&1\end{pmatrix}\cdot \begin{pmatrix}1&0&2\\0&1&1\\1&2&3\end{pmatrix}\cdot\begin{pmatrix}1&1&1\\0&1&1\\0&0&1\end{pmatrix}=\begin{pmatrix}1&0&1\\-1&-2&-4\\1&3&6\end{pmatrix}$

Theorem: For a linear map $h:V\to W$ with rank $k$, there exists bases $B$ and $D$ such that $\text{Rep}_{B,D}(h)=\left(\begin{array}{c|c}I_k&Z\\\hline Z&Z\end{array}\right)$

Let $V$ have dimension $n$ and $W$ have dimension $m$.
$\implies\text{nullity}(h)=n-k$
$\implies$ we can find $n-k$ vectors $\vec{\beta}_{k+1},...,\vec{\beta}_n$ that form a basis for $\mathscr{N}(h)\subset V$
$\implies$ those vectors can be extended to $B=\langle\vec{\beta}_1,...,\vec{\beta}_k,\vec{\beta}_{k+1},...,\vec{\beta}_n\rangle$
$\implies\mathscr{R}(h)=\text{span}\{h(\vec{\beta}_1),...,h(\vec{\beta}_k),h(\vec{\beta}_{k+1}),...,h(\vec{\beta}_n)\}\subset W$
$\implies\mathscr{R}(h)=\text{span}\{h(\vec{\beta}_1),...,h(\vec{\beta}_k)\}$ since $h(\vec{\beta}_i)=\vec{0}$ for $i=k+1,...,n$
$\implies\vec{\delta}_1=h(\vec{\beta}_1),...,\vec{\delta}_k=h(\vec{\beta}_k)$ form a basis for $\mathscr{R}(h)$
$\implies$ can be extended to basis $D=\langle\vec{\delta}_1,...,\vec{\delta}_k,\vec{\delta}_{k+1},...,\vec{\delta}_n\rangle$ of $W$
Thus, we have $h(\vec{\beta}_i)=\vec{\delta}_i$ for $i=1,...,k$ and $h(\vec{\beta}_i)=\vec{0}$ for $i=k_1,...,n$, so we have found $B$ and $D$ such that
$\text{Rep}_{B,D}(h)=\left(\begin{array}{c|c}I_k&Z\\\hline Z&Z\end{array}\right)$
as desired.

Theorem: any $m\times n$ matrix is matrix equivalent to a $m\times n$ matrix of the form $\left(\begin{array}{c|c}I&Z\\\hline Z&Z\end{array}\right)$

Suppose $M$ is an $m\times n$ matrix. For a linear map $h:V\to W$ and appropriate bases $B_1$ of $V$ and $D_1$ of $W$, we have $M=\text{Rep}_{B_1,D_1}(h)$.
From the previous theorem, we can find bases $B$ of $V$ and $D$ of $W$ such that $\text{Rep}_{B,D}(h)=\left(\begin{array}{c|c}I_k&Z\\\hline Z&Z\end{array}\right)$.
These represent the same linear map under different bases, so they are matrix equivalent.

First recall the elementary row operation matrices act on rows if multiplied on the left and on columns if multiplied on the right.

For a matrix $M$, we can apply row-reduction to get an (not reduced) echelon form matrix $R$. Combine those reduction matrices (with right-to-left multiplication) to a single matrix $P$. Thus, we have $PM=R$.
Then column-reduce $R$ to get a matrix in block partial-identity form. Combine those operations (with left-to-right multiplication) to get a matrix $Q$. So, we have $PMQ=RQ=\left(\begin{array}{c|c}I&Z\\\hline Z&Z\end{array}\right)$

Consider this rank $2$ matrix
$M=\begin{pmatrix}1&2&3\\4&5&6\\7&8&9\end{pmatrix}$
We will find $P$ and $Q$ such that $PMQ$ is the canonical matrix of rank $2$.
Row reducing gives
$\begin{pmatrix}1&2&3\\4&5&6\\7&8&9\end{pmatrix}\xrightarrow[-7\rho_1+\rho_3]{-4\rho_1+\rho_2}\space\xrightarrow{-2\rho_2+\rho_3}\space\xrightarrow{-1/3\rho_2}\begin{pmatrix}1&2&3\\0&1&2\\0&0&0\end{pmatrix}$
So we have (note right to left)
$P=\begin{pmatrix}1&0&0\\0&-1/3&0\\0&0&1\end{pmatrix}\begin{pmatrix}1&0&0\\0&1&0\\0&-2&1\end{pmatrix}\begin{pmatrix}1&0&0\\-4&1&0\\-7&0&1\end{pmatrix}=\begin{pmatrix}1&0&0\\4/3&-1/3&0\\1&-2&1\end{pmatrix}$
Next we perform column operations
$\begin{pmatrix}1&2&3\\0&1&2\\0&0&0\end{pmatrix}\xrightarrow{-2\text{col}_2+\text{col}_3}\space\xrightarrow[\text{col}_1+\text{col}_3]{-2\text{col}_1+\text{col}_2}\begin{pmatrix}1&0&0\\0&1&0\\0&0&0\end{pmatrix}$
So (note left to right)
$Q=\begin{pmatrix}1&0&0\\0&1&-2\\0&0&1\end{pmatrix}\begin{pmatrix}1&-2&1\\0&1&0\\0&0&1\end{pmatrix}=\begin{pmatrix}1&-2&1\\0&1&-2\\0&0&1\end{pmatrix}$
In sum, we have $M$ being row equivalent to
$PMQ=\begin{pmatrix}1&0&0\\4/3&-1/3&0\\1&-2&1\end{pmatrix}\begin{pmatrix}1&2&3\\4&5&6\\7&8&9\end{pmatrix}\begin{pmatrix}1&-2&1\\0&1&-2\\0&0&1\end{pmatrix}=\begin{pmatrix}1&0&0\\0&1&0\\0&0&0\end{pmatrix}$